package 复习.博客2.递归和回溯;

import java.util.ArrayList;
import java.util.Arrays;

public class 有重复数字的全排列 {
    ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        boolean[] flag = new boolean[num.length];
        Arrays.fill(flag,false);
        Arrays.sort(num);
        bakcStacking(num,flag);
        return lists;
    }

    public void bakcStacking(int[] num,boolean[] flag){
        if(list.size() == num.length){
            lists.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < num.length; i++) {
            if(i > 0 && num[i] == num[i - 1] && flag[i - 1] == false){
                continue;
            }
            if(flag[i] == false){
                flag[i] = true;
                list.add(num[i]);
                bakcStacking(num,flag);
                list.remove(list.size() - 1);
                flag[i] = false;
            }
        }
    }
}

/*
public class Solution {
    ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        boolean[] arr = new boolean[num.length];
        Arrays.fill(arr,false);
        Arrays.sort(num);
        backstacking(num,arr);
        return lists;
    }

    public void backstacking(int[] nums,boolean[] arr){
        if(list.size() == nums.length){
            lists.add(new ArrayList<>(list));
        }

        for (int i = 0; i < nums.length; i++) {
            if(i > 0 && nums[i] == nums[i - 1] && arr[i - 1] == false) continue;
            if(arr[i] == false){
                list.add(nums[i]);
                arr[i] = true;
                backstacking(nums,arr);
                arr[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}
 */
